package org.example.greedy;
//https://leetcode.cn/problems/longest-increasing-subsequence/
import java.util.ArrayList;
import java.util.List;
//300. 最长递增子序列
//O(N*logN)
class Solution {
    //贪心 + 二分查找
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        List<Integer> hash = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            int val = nums[i];
            int left = 0, right = hash.size() - 1;
            //hash为空
            //新元素比所有元素都大时，直接插入到最后
            if(hash.size() == 0 || val > hash.get(right)) {
                hash.add(val);
                continue;
            }
            //二分插入位置（hash为有序数组）
            while(left < right) {
                int mid = left + (right - left) / 2;
                if(hash.get(mid) < val) left = mid + 1;
                else right = mid; 
            }
            hash.set(left, val);
        }
        return hash.size();
    }
}